package main

import (
   "fmt"
   "sort"
)

//
//func checkInclusion(s1, s2 string) bool {
//	if len(s1) > len(s2) {
//		return false
//	}
//	cnt1, cnt2 := [26]int{}, [26]int{}
//	for i := range s1 {
//		cnt1[s1[i]-'a']++
//		cnt2[s2[i]-'a']++
//	}
//	for i := 0; i < len(s2)-len(s1); i++ {
//		if cnt1 == cnt2 {
//			return true
//		}
//		cnt2[s2[i]-'a']--
//		cnt2[s2[i+len(s1)]-'a']++
//	}
//	return cnt1 == cnt2
//}
//func findMaxAverage(nums []int, k int) float64 {
//	sort.Ints(nums)
//	var res float64
//	var ress float64
//	s :=nums[len(nums)-k-1:]
//	for _,v:=range s {
//		res +=float64(v)
//	}
//	ress = res/float64(k)
//	return ress
//}

//type TreeNode struct {
//	Val  int
//	Left *TreeNode
//	Right *TreeNode
//}
//
//func sumNumber(root *TreeNode )int {
//  var dfs func (node *TreeNode,PrevSum int)int
//  dfs = func(node *TreeNode,PrevSum int)int{
//	  if root ==nil{
//		  return 0
//	  }
//	  sum :=PrevSum *10 +root.Val
//	  if root.Left ==nil && root.Right == nil{
//		  return sum
//	  }
//	  a :=dfs(root.Left,PrevSum)
//	  b :=dfs(root.Right,PrevSum)
//	  return a+b
//  }
//    res :=dfs(root,0)
//    return res
//}
//
//func dfs(root *TreeNode,PrevSum int)int{
//	if root ==nil{
//		return 0
//	}
//	sum :=PrevSum *10 +root.Val
//	if root.Left ==nil && root.Right == nil{
//		return sum
//	}
//	return dfs(root.Left,sum)+dfs(root.Right,sum)
//
//}
type TreeNode struct {
   Right  *TreeNode
   Left *TreeNode
   Val int
}
//
//
//var res []int
//
//func rightSideView(root *TreeNode) []int {
//   res = []int{}
//   dfs(root, 1)
//   return res
//}
//
//func dfs(root *TreeNode, level int) {
//   if root == nil {
//      return
//   }
//
//   if level > len(res) {
//      res = append(res, root.Val)
//   }
//
//   dfs(root.Right, level+1)
//   dfs(root.Left, level+1)
//}


func rightSideView(root *TreeNode) []int {
   var res []int
   if root == nil {
      return res
   }
   queue := []*TreeNode{root}
   for len(queue) != 0 {
      levelSize := len(queue)
      res = append(res, queue[levelSize-1].Val)
      for i:=0;i<levelSize;i++{
         node := queue[0]
         queue = queue[1:]
         if node.Left != nil {
            queue = append(queue, node.Left)
         }
         if node.Right != nil {
            queue = append(queue, node.Right)
         }
      }
   }
   return res
}


//func rightSideView(root *TreeNode) []int{
//   var res []int
//   if root == nil {
//      return res
//   }
//
//   queue :=[]*TreeNode{root}
//   for len(queue) !=0{
//      levelSize :=len(queue)
//      res =append(res , queue[levelSize-1].Val)
//      for i:=0;i<levelSize;i++{
//         node :=queue[0]
//         queue:=queue[1:]
//         if node.Left !=nil{
//            queue =append(queue,node.Left)
//         }
//         if node.Right !=nil {
//            queue =append(queue,node.Right)
//         }
//      }
//   }
//   return res
//}


func kthSmallest(root *TreeNode, k int) int {

   arr := []int{}
   find(root, &arr)

   return arr[k-1]

}
func find(root *TreeNode, arr *[]int) {

   if root == nil {
      return
   }

   find(root.Left, arr)
   *arr = append(*arr, root.Val)
   find(root.Right, arr)
   return

}

func kthSmallest(root *TreeNode, k int) int {
   res:=[]int{}
   var dfs func(root *TreeNode)
   dfs=func(root *TreeNode){
      if root==nil{
         return
      }
      dfs(root.Left)
      res=append(res,root.Val)
      dfs(root.Right)
   }
   dfs(root)
   sort.Ints(res)
   //fmt.Print(res)
   return res[k-1]
}



func main(){
	//s1 :="ab"
	//s2 :="eidbaooo"
	//fmt.Println(checkInclusion(s1,s2))
   x:=make([]int,2,2)
   fmt.Printf(x)
   x:=append(x,3)

}
